#pragma once // 指示只包含一次头文件，防止重复包含
#define _CRT_SECURE_NO_WARNINGS // 禁用某些安全警告
#include <stdio.h> // 标准输入输出头文件
#include <stdlib.h> // 标准库头文件
#include <iostream> // C++ 风格的输入输出流
#include <vector> // 动态数组容器
#include <string> // 字符串类
#include <cmath> // 数学函数库
#include <iomanip> // 用于格式化输入输出
#include <climits> // 定义各种限制，如 INT_MAX
using namespace std; // 使用标准命名空间

// 打印邻接矩阵的函数
void Print_Graph(const vector<vector<int>>& graph, const string& V_name) {
    int V = V_name.size(); // 顶点的数量
    cout << "对应矩阵为：\n";
    cout << "    "; // 顶部的空格用于对齐列标题
    for (int i = 0; i < V; i++) {
        cout << setw(4) << V_name[i]; // setw(4) 用于设置宽度，保持列对齐
    }
    cout << "\n";

    for (int i = 0; i < V; i++) {
        cout << setw(4) << V_name[i]; // 行标题
        for (int j = 0; j < V; j++) {
            if (graph[i][j] == 0) {
                cout << setw(4) << "0"; // setw(4) 用于设置宽度，保持列对齐
            }
            else if (graph[i][j] == INT_MAX) {
                cout << setw(4) << "∞"; // setw(4) 用于设置宽度，保持列对齐
            }
            else {
                cout << setw(4) << graph[i][j]; // setw(4) 用于设置宽度，保持列对齐
            }
        }
        cout << "\n";
    }
}

// Dijkstra算法求最短路径的函数
void Dijkstra(const vector<vector<int>>& graph, int src, vector<int>& dist, vector<int>& prev) {
    int V = graph.size(); // 顶点的数量
    vector<bool> sptSet(V, false); // 标记是否已经找到最短路径
    dist.assign(V, INT_MAX); // 距离数组初始化为无穷大
    prev.assign(V, -1); // 前驱节点数组初始化为-1

    dist[src] = 0; // 起始顶点到自己的距离为0

    for (int count = 0; count < V - 1; count++) {
        int u = -1;
        int minDistance = INT_MAX;

        // 选择未处理的顶点中距离最小的顶点
        for (int v = 0; v < V; v++) {
            if (!sptSet[v] && dist[v] < minDistance) {
                minDistance = dist[v];
                u = v;
            }
        }

        sptSet[u] = true; // 标记为已处理

        // 更新相邻顶点的距离
        for (int v = 0; v < V; v++) {
            if (!sptSet[v] && graph[u][v] != INT_MAX && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
                prev[v] = u;
            }
        }
    }
}

// 递归打印最短路径的函数
void Print_Path(const vector<int>& prev, int v, const string& V_name) {
    if (prev[v] == -1) {
        cout << V_name[v];
        return;
    }
    Print_Path(prev, prev[v], V_name);
    cout << " -> " << V_name[v];
}

int main() {
    int V, E; // 顶点与边数
    cin >> V >> E;

    string V_name; // 顶点的名字
    cin >> V_name;

    // 构建邻接矩阵，并初始化为INT_MAX（表示无连接）
    vector<vector<int>> graph(V, vector<int>(V, INT_MAX));

    // 初始化邻接矩阵的对角线元素为0（顶点到自己的距离为0）
    for (int i = 0; i < V; i++) {
        graph[i][i] = 0;
    }

    //给边加上权重
    for (int i = 0; i < E; i++) {
         string u;
         int weight;
         cin >> u >> weight;
         int u_index = u[0] - 'A';
         int v_index = u[1] - 'A';
         graph[u_index][v_index] = weight;
    }

    // 打印邻接矩阵
    Print_Graph(graph, V_name);

    // 运行Dijkstra算法
    vector<int> dist, prev;
    int src = 0; // 假设从顶点A开始
    Dijkstra(graph, src, dist, prev);

    // 打印最短路径结果
    cout << "最短路径为:" << endl;
    for (int i = 1; i < V; i++) {
        if (dist[i] == INT_MAX) {
            cout << "A到" << V_name[i] << "无路径" << endl;
        }
        else {
            cout << "A到" << V_name[i] << "最短路径: ";
            Print_Path(prev, i, V_name);
            cout << " 长度为 " << dist[i] << endl;
        }
    }

    return 0;
}